The present invention is directed, in general, to adder and multiplier circuits and, more specifically, to adder and multiplier circuits employing logic gates having discrete, weighted inputs, combinations of the same, methods of performing combinatorial operations with such logic gates and combinations thereof.
Digital systems are used extensively in computation and data processing, controls, communications and measurement. Digital systems use digital signals that may only assume discrete values. Typically, digital systems use binary signals that employ only two values. Since such systems only use two distinct values, errors caused by component variations are minimized. As a result, a digital system may be designed such that, for a given input, an output thereof is exactly correct and repeatable. This gives rise to the extreme accuracy for which digital systems are well known.
Analog systems, on the other hand, use analog signals that vary continuously over a specified range. Analog systems are thus particularly vulnerable to error, depending on the accuracy of the components used therein. Since digital systems are generally capable of greater accuracy and reliability than analog systems, many tasks formerly performed by analog systems are now performed exclusively by digital systems.
A digital system, such as a computer, typically includes an input device, an output device, a processor or central processing unit (CPU) and a data storage device (e.g., random access memory or hard disk). A CPU typically contains an arithmetic/logic unit (ALU) that performs arithmetic functions (e.g., add, subtract, multiply and divide) and logic functions (e.g., AND, OR and NOT). Additionally, a CPU may also contain a floating point unit (FPU) that performs floating point operations (e.g., add, subtract, multiply and divide).
One basic building block of digital systems is a logic gate. Conventional logic gates have one output and one or more inputs. The number of inputs is called the xe2x80x9cfan-inxe2x80x9d of the gate. The state of the output is completely determined by the state(s) of the input(s).
Logical and arithmetic functions are typically performed by a number of logic gates coupled together to form a multi-layer network. The maximum number of gates cascaded in series between the input and the output of such a network is typically referred to as the number of layers of gates. Designers are concerned with the number of layers in a network for several reasons. In some applications, increasing the number of layers may reduce the required number of gates and gate inputs (i.e., fan-in), thus reducing the cost (which may be expressed in terms of integrated circuit area) of building the network. Of course, cascading a large number of gates together may result in unacceptable input-output delays and data dependency conditions. When the input of a gate is switched, a finite time elapses before the output of the gate changes. If a large number of gates are cascaded together to form a network, the time between an input change and a corresponding change in the network output may become excessive, thereby slowing down the operation of the network.
Arithmetic functions are particularly susceptible to the effects of cascaded gates. The serial solution for binary addition is given here as an example. Initially, a first augend bit and a first addend bit are added together, to produce a first sum bit and a first carry bit. The first carry bit is then added to the second augend and addend bits to produce the second sum and carry bits. Since the second sum bit is dependent on the value of the first carry bit, the second sum bit cannot be computed before the first carry bit is computed. While each input-output delay is small, the cumulative input-output delay perceived when adding large numbers, due to the propagation of the carry bit, is proportional to the number of bits added, and may be prohibitive. Techniques (e.g., carry look-ahead, conditional sum or prefix computation have been developed for reducing the delay to a logarithmic function of the number of input bits to be added. The number of Boolean gates (e.g., AND, OR or NOT) used by such techniques is in the range of from 8n to 35n or 2n log(n) to 3n log(n), where n is the number of bits to be added and the logarithms are base two.
Increasing processing power is a continuing goal in the development of microprocessors. Microprocessor designers are generally familiar with three ways to increase the processing power of a CPU. The CPU""s clock frequency may be increased so that the CPU can perform a greater number of operations in a given time period. Microprocessors are designed to operate at increasingly high clock frequencies. For instance, the 8080 (introduced in 1974 by the Intel Corporation) was designed to operate at about 2 to 3 MHZ. Today, Intel""s Pentium II line of processors are designed to operate with clock frequencies over 300 MHZ. While a higher clock frequency generally results in increased processing power, the higher clock frequency also increases power dissipation, resulting in higher device operating temperatures. Microprocessor designers, therefore, must address these additional problems to avoid catastrophic device failures.
Another way to increase processing power is to increase input and output data bus width, thereby allowing the CPU to process a greater amount of code and data. Early microprocessors were packaged using dual in-line packaging (DIP) technology. Increasing the width of the data buses was both expensive and unrealistic, often resulting in extremely large device packages. Today, with the use of pin grid array (PGA) packaging, increasing the size of the data buses no longer poses a packaging problem. Of course, a larger number of transistors is required to process the additional information conveyed by the wider data buses.
Yet another way to increase processing power is to change the internal architecture of the microprocessor to overlap the execution of instructions by, for example, superscaling. This method also requires the addition of a large number of transistors, since entire processing stages or execution units must be duplicated. Performing a large number of instructions in parallel may also result in data dependency problems.
Accordingly, what is needed in the art is new architectures for addition circuitry, multiplication circuitry and combinations of the same that increase the processing power of conventional digital systems.
To address the above-discussed deficiencies of the prior art, the present invention provides a circuit and method for deriving an adder output bit (such as a carry out bit, a carry-generate bit or a carry-propagate bit) from adder input bits (such as a carry in bit, (at least) first and second addend and augend bits, (at least) first and second carry-generate bits or (at least) first and second carry-propagate bits. The present invention further provides a multiplier circuit, a method of multiplying, a microprocessor and digital signal processor (DSP) employing the circuit or the method and a method of generating weights for logic gates.
In one embodiment, the circuit includes: (1) first, second and third logic gates that generate intermediate bits based on threshold comparisons of concatenations of ones of the adder input bits and (2) combinatorial logic that generates the adder output bit from the intermediate bits. Circuits may be coupled to one another in layers to yield a wider adder. In such configuration, addend and augend bits are transformed into carry-generate and carry-propagate bits, which are ultimately transformed into a carry out bit.
The present invention introduces novel digital addition and multiplication circuits that take advantage of multiple discrete logic levels to perform respective addition and multiplication operations significantly faster than prior art adders and multipliers. Of course, the principles of the present invention extend to cover logic gates that process more than two adder input bits concurrently.
In one embodiment of the present invention, the first logic gate generates a first intermediate bit based on a comparison between a concatenation of ones of the adder input bits and zero. In a related embodiment of the present invention, the second logic gate generates a second intermediate bit based on a comparison between a concatenation of ones of the adder input bits and two. In another related embodiment of the present invention, the third logic gate generates a third intermediate bit based on a comparison between a concatenation of ones of the adder input bits and four.
The first, second and third logic gates cooperate to provide the correct intermediate bits to the combinatorial circuitry based on the values of the various adder input bits.
In one embodiment of the present invention, the combinatorial logic comprises first, second and third AND gates and first and second OR gates coupled to outputs thereof. In an embodiment of the invention to be illustrated and described, the combinatorial logic generates the adder output bit by additionally employing the ones of the adder input bits.
In one embodiment of the present invention, each of the first, second and third logic gates includes: (1) a summer, having at least two binary inputs with corresponding discrete weights, that generates a weighted sum of input binary digits presented at the at least two binary inputs and (2) a quantizer, coupled to the summer, that generates an output binary digit at a binary output thereof that is a function of the weighted sum. In this embodiment, the logic gates employ an internal representation having more than two logic levels to perform combinatorial operations, but nonetheless have purely binary inputs and outputs. The binary inputs and outputs ensure that the logic gates can be employed in an otherwise conventional binary digital architecture without requiring the architecture to be modified apart from insertion of the logic gates or circuits that employ the logic gates in combination with more conventional gates, e.g., Boolean gates.
In one embodiment of the present invention, the discrete weights are integer multiples of a predetermined number. The predetermined number may be xe2x80x9c1,xe2x80x9d allowing the discrete weights to assume integer values. Of course, the predetermined number may be any suitable number.
In one embodiment of the present invention, each of the at least two binary inputs includes: (1) a current source capable of producing a substantially constant electrical current corresponding to a particular discrete weight and (2) a switch, coupled to the current source, that switches the electrical current as a function of a corresponding particular input binary digit. The current source may be derived from a voltage source by way of a resistance. The voltage source may be provided by a power supply that provides power to other logic circuitry (such as other microprocessor circuitry) that may surround, and interact with, the logic gate. For purposes of the present invention, xe2x80x9csubstantially constant electrical currentxe2x80x9d is defined to be sufficiently constant such that the accuracy of the logic gate is not adversely affected. The level of precision required of the current is or can be a function of the range of discrete integer weights employed in the logic gate.
In one embodiment of the present invention, the circuit further includes a threshold input that provides a threshold number to the quantizer, the output binary digit being a function of a relationship between the weighted sum and the threshold number. The threshold number provides a bias to the quantizer, allowing a threshold between the binary output states to assume a value other than zero. In an embodiment to be illustrated and described, the discrete weights are advantageously selected to minimize (ideally to zero) the threshold number. This has the advantage of minimizing the number or size of current sources or sinks and thus potentially reducing the area (and therefore the cost) of the logic gate.
In one embodiment of the present invention, the corresponding discrete weights are provided by a selected one of: (1) current sources and (2) current sinks. The current sources may be made to correspond to positive discrete weights and the current sinks may be made to correspond to negative discrete weights, such that currents are added and subtracted in the summer to obtain the desired weighted sum. In this way, the logic gates of the present invention can be adapted to operate with respect to discrete weights of either positive or negative sign or a combination thereof.
In one embodiment of the present invention, the minimum integer weights and thresholds determining the threshold gates of arbitrary fan-ins able to compute the group carry-generate bit from multiple carry-generate and carry-propagate bits are also presented together with the method of determining them for gates of arbitrary fan-ins (larger than two).
In one embodiment of the present invention, the circuit further includes a plurality of other of the circuits coupled together to form a multiplier circuit. Those skilled in the art will readily perceive other highly advantageous applications for the logic gates of the present invention. The present invention fully encompasses all applications.
The present invention further provides a multiplier circuit, including a summer having at least two inputs with corresponding weights, the inputs corresponding to bits of a multiplicand, the weights based on a multiplier, the summer generating a weighted sum of the multiplicand. The weighted sum represents the result of a multiplication of the multiplier and the multiplicand and is analog in nature. A digital equivalent of the weighted sum may be derived by either successive comparisons with known analog levels (thereby producing a succession of result bits) or by converting the analog weighted sum to a digital number in an analog-to-digital (A/D) converter. The weights are preferably created by bit-shifting the multiplier. A bias may also be applied to the multiplier circuit to accommodate equations of the type: Axc3x97B+C; called inner product or multiply accumulate.
The foregoing has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.